<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML>
<HEAD>
   <TITLE>prob016: traffic lights</TITLE>
</HEAD>
<BODY>

<HR><!------------------------------------------------------------------------>
<CENTER>
<H1>
prob016: traffic lights</H1></CENTER>

<CENTER><TABLE>
<TR>
<TD>proposed by&nbsp;</TD>

<TD ALIGN=LEFT><B><A HREF="http://www.cs.york.ac.uk/~tw">Toby Walsh</A></B>
<ADDRESS>
<A HREF="mailto:tw@cs.york.ac.uk">tw@cs.york.ac.uk</A></ADDRESS>
</TD>
</TR>
</TABLE></CENTER>


<HR><!------------------------------------------------------------------------>
<H3>
Results</H3>
Only 2<SUP>2</SUP> out of the 2<SUP>12</SUP> possible assignments are solutions.
<P>(V1,P1,V2,P2,V3,P3,V4,P4) = {(r,r,g,g,r,r,g,g), (ry,r,y,r,ry,r,y,r),
(g,g,r,r,g,g,r,r), (y,r,ry,r,y,r,ry,r)}
<P>The problem has relative few constraints, but each is very tight. Local
propagation appears to be rather ineffective on this problem.
<BR>&nbsp;
<P>
<HR><!------------------------------------------------------------------------>
<UL><A HREF="../../index.html">Back</A> to CSPLib
home page.</UL>

</BODY>
</HTML>
